package com.zwy.Algorithm;

/*
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，
它所做出的仅仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解
，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
 */
//使用贪心算法解决条约游戏
/*
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。
 */
public class greedy {
    public static void main(String[] args) {
        Solution solution = new greedy().new Solution();
        int []arr={0};
        boolean b = solution.canJump(arr);
        System.out.println(b);

    }
    class Solution {

        public boolean canJump(int []nums) {
            int []maxPoint=new int[nums.length];
            int max=nums[0];
            maxPoint[0]=nums[0];
            for (int i = 1; i < nums.length; i++) {
                if(max>=i){
                    maxPoint[i]=i+nums[i];
                    max=Math.max(max,maxPoint[i]);
                }
            }
            return max>=nums.length-1?true:false;
        }

    }
}
